class LNode(object):
    def __init__(self, data, p=0):
        self.data = data
        self.next = p


class LinkList(object):
    def __init__(self):
        self.head = None

    def initList(self, data):
        self.head = LNode(data[0])
        p = self.head
        for i in data[1:]:
            node = LNode(i)
            p.next = node
            p = p.next

    def isEmpty(self):
        if self.head.next == 0:
            print("Empty list!")
        else:
            return 0

    def getLength(self):
        if self.isEmpty():
            exit(0)

        p = self.head
        len = 0
        while p:
            len += 1
            p = p.next
        return len

    def traveList(self):
        if self.isEmpty():
            exit(0)
        print("\rlink list traving result")
        p = self.head
        while p:
            print(p.data)
            p = p.next

    def insertElem(self, key, index):
        if self.isEmpty():
            exit(0)
        if index < 0 or index > self.getLength() - 1:
            print("\rKey Error!")
            exit(0)

        p = self.head
        i = 0
        while i <= index:
            pre = p
            p = p.next
            i += 1

        node = LNode(key)
        pre.next = node
        node.next = p

    def deleteElem(self, index):
        if self.isEmpty():
            exit(0)
        if index < 0 or index > self.getLength() - 1:
            print("\rValue Error! Program Exit.")
            exit(0)

        i = 0
        p = self.head
        # 遍历找到索引值为 index 的结点
        while p.next:
            pre = p
            p = p.next
            i += 1
            if i == index:
                pre.next = p.next
                p = None
                return 1

        # p的下一个结点为空说明到了最后一个结点, 删除之即可
        pre.next = None

    def ReverseLisr(self):
        if self.isEmpty():
            exit(0)
        p = self.head
        cur = self.head.next
        p.next = None
        while cur:
            tmp = cur.next
            cur.next = p
            p = cur
            cur = tmp
        self.head = p

    def mergeTwoLists(self, l1, l2):
        if l1 == None:
            return l2
        elif l2 == None:
            return l1
        elif l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

    def deleteDuplicates(self):
        head = self.head
        whole = head
        nums = {}
        if head == None:
            return
        while head:
            if head.data not in nums:
                nums[head.data] = head.data
                prev = head
                head = head.next
            else:
                prev.next = head.next
                head = head.next
        return(whole)

    def removeElements(self, val):
        head = self.head
        dummy = self.initList([0])
        dummy.next = head
        prev = dummy
        last = prev.next
        while last :
            if last.data == val:
                prev.next = last.next
                last = prev.next
            else:
                prev = prev.next
                last = prev.next
        return dummy.next




data1 = [1,2,6,3,4,5,6]
data2 = [1, 3, 5]
l = LinkList()
l1 = l.initList(data1)

l.traveList()
# l.deleteDuplicates()
print(l.removeElements(6))

# l.insertElem(666,3)
# l.deleteElem(3)
# l.ReverseLisr()
# l.traveList()